import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.logging.Level;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-03-20
 * Time: 23:09
 */


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


class Solution {
    // public List<Integer> rightSideView(TreeNode root) {
    //     List<Integer> ans=new ArrayList<>();
    //     if(root==null){
    //         return ans;
    //     }
    //     Queue<TreeNode> queue=new LinkedList<>();
    //     queue.add(root);
    //     while(!queue.isEmpty()){
    //         int size=queue.size();
    //         TreeNode temp=queue.peek();
    //         ans.add(temp.val);
    //         for (int i = 0; i < size; i++) {
    //             temp=queue.poll();
    //             // 先右后左减少了不必要的判断
    //             if(temp.right!=null){
    //                 queue.add(temp.right);
    //             }
    //             if(temp.left!=null){
    //                 queue.add(temp.left);
    //             }
    //         }
    //     }
    //     return ans;
    // }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans=new ArrayList<>();
        if(root==null){
            return ans;
        }
        dfs(ans, 0, root);
        return ans;
    }

    public void dfs(List<Integer> ans, int height, TreeNode root){
        if(root==null){
            return;
        }
        if(height==ans.size()){
            ans.add(root.val);
        }
        // 先右后左减少了不必要的比较
        dfs(ans , height+1,root.right);
        dfs(ans , height+1,root.left);
    }
}